#include <stdio.h>  //头文件用于输入输出操作
#include <stdlib.h> //用于malloc函数

#define TElemType int //定义树的元素类型为int
#define OK 1 //定义成功状态码
#define ERROR 0 //定义失败状态码
#define OVERFLOW -2 //定义溢出状态码

typedef int Status; //定义状态类型

typedef struct BiTNode //定义二叉树结点结构
{
    TElemType data; //结点数据
    struct BiTNode *lchild, *rchild; //左右孩子指针
} BiTNode, *BiTree; //定义二叉树指针

//创建二叉树
Status CreateBiTree(BiTree *T) 
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#') //若输入#则表示空树
        *T=NULL;//置空树指针
    else
    {
        *T=(BiTree)malloc(sizeof(BiTNode));//分配内存
        if(!*T) //若分配内存失败
            return OVERFLOW;//返回溢出状态码
        (*T)->data=ch;//为根结点赋值
        CreateBiTree(&((*T)->lchild));//递归创建左子树
        CreateBiTree(&((*T)->rchild));//递归创建右子树
    }
    return OK; //返回成功状态码
}

//先序遍历递归函数
void preorderTraversal(BiTree root)
{
    if(root==NULL)//若树为空则返回
        return;
    printf("%c ",root->data);//先序遍历打印结点数据
    preorderTraversal(root->lchild);//递归左子树
    preorderTraversal(root->rchild);//递归右子树
}

//中序遍历递归函数
void inorderTraversal(BiTree root)
{
    if(root==NULL)//若树为空则返回
        return;
    inorderTraversal(root->lchild);//递归左子树
    printf("%c ",root->data);//中序遍历打印结点数据
    inorderTraversal(root->rchild);//递归右子树
}

//后序遍历递归函数
void postorderTraversal(BiTree root)
{
    if(root==NULL)//若树为空则返回
        return;
    postorderTraversal(root->lchild);//递归左子树
    postorderTraversal(root->rchild);//递归右子树
    printf("%c ",root->data);//后序遍历打印结点数据
}

//定义栈结构
#define MAXSIZE 100 //定义栈最大容量
typedef struct 
{
    BiTree *data[MAXSIZE]; //定义栈元素类型为二叉树指针
    int top; //栈顶指针
} SqStack;//定义栈类型
Status InitStack(SqStack *s) //初始化栈
{
    s->top=-1; //置栈顶指针为-1
    return OK; //返回成功状态码
};
Status StackEmpty(SqStack s) //判断栈是否为空
{
    if(s.top==-1) //若栈顶指针为-1则为空栈
        return OK; //返回成功状态码
    else
        return ERROR; //返回失败状态码
};
Status Push(SqStack *s, BiTree *e) //入栈
{
    if(s->top==MAXSIZE-1) //若栈满则溢出
        return ERROR; //返回失败状态码
    s->data[++s->top]=e; //将元素e入栈, 指针加1
    return OK; //返回成功状态码
};
Status Pop(SqStack *s, BiTree *e) //出栈
{
    if(s->top==-1) //若栈空则返回
        return ERROR; //返回失败状态码
    *e=s->data[s->top--]; //取出栈顶元素, 指针减1
    return OK; //返回成功状态码
};
//获取栈顶元素
Status GetTop(SqStack s, BiTree **e)
{
    if(s.top==-1) //若栈空则返回
        return ERROR; //返回失败状态码
    *e=s.data[s.top]; //否则取出栈顶元素
    return OK; //返回成功状态码
};
//中序遍历非递归算法
Status InOrderTraverse(BiTree T)
{
    SqStack s;//定义栈
    BiTNode *p;//定义指针
    InitStack(&s);//初始化栈
    Push(&s,T);//入栈根结点
    while(!StackEmpty(s))//若栈不空
    {
        while(GetTop(s,&p))
        {
            if(p)//若指针不为空
                Push(&s,p->lchild);//入栈左子树
            else
                break;//若指针为空则跳出循环
        }
        Pop(&s,&p);//出栈
        if(!StackEmpty(s))//若栈不空
        {
            Pop(&s,&p);//出栈
            printf("%c ",p->data);//打印结点数据
            Push(&s,p->rchild);//入栈右子树
        }
    }
    return OK; //返回成功状态码
}

Status InOrderTraverse2(BiTree T)
{
    SqStack s;//定义栈s，用于存储二叉树的节点
    BiTNode *p;//定义指针p，用于遍历二叉树的节点
    InitStack(&s);//初始化栈s，确保栈为空
    p=T;//初始化指针p，指向根节点
    while(p ||!StackEmpty(s))//若二叉树不空或栈不空
    {
        if(p)//若指针p不为空,将节点压入栈
        {
            Push(&s,p);//将指针p入栈
            p=p->lchild;//指向左子树，继续遍历
        }
        else//若指针p为空,则出栈并打印节点数据
        {
            Pop(&s,&p);//出栈
            printf("%c ",p->data);//打印结点数据
            p=p->rchild;//指向右子树，继续遍历
        }
    }
    return OK; //返回成功状态码
}

//测试函数
int main()
{
    BiTree T;
    printf("请输入二叉树的先序序列(#表示空节点)：");
    CreateBiTree(&T);
    printf("先序遍历：");
    preorderTraversal(T);
    printf("\n");
    printf("中序遍历：");
    inorderTraversal(T);
    printf("\n");
    printf("后序遍历：");
    postorderTraversal(T);
    printf("\n");

    return 0;//返回0表示程序正常结束
}